
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* arrs_sort(const int *arr,const int* brr,const int sz1,const int sz2)//这里会申请动态太内存，调用函数请记得释放 ,返回数组的大小一定就是sz1+sz2 
{
	int* rearrs = (int*)malloc(sizeof(int)*(sz1+sz2));
	int c = 0; 
	int a = 0,b = 0;
	int sign = a<sz1 ;
    sign += b<sz2;
	while(sign)
	{
		switch(sign)
	{
		case 2:
			{
				if(arr[a]>brr[b])
				{
					rearrs[c++] = brr[b++];
				}
				else
				{
					rearrs[c++] = arr[a++];
				}
				break;
				
			}
		case 1:{
			if(a<sz1)
			{
				rearrs[c++] = arr[a++];
			}
			else if (b<sz2)
			{
				rearrs[c++] = brr[b++];
			}
			break;
		}
		default :break;
	}
    sign = a<sz1;
    sign += b<sz2;
	}
	return rearrs; 
} 
//归并排序
//迭代版本

int merge_sort(int arr[],int sz)
{
    int a = 2;
    for(;a/2<sz;a*=2)
    {
        for(int i=0;i<sz;i+=a)
        {
            if(i+a<=sz)
            {
                int *t = arrs_sort(&arr[i],&arr[i+a/2],a/2,a/2);
                memmove(&arr[i],t,a*sizeof(int));
                free(t);
            }
            else if(i+a/2<sz)
            {
                int *t = arrs_sort(&arr[i],&arr[i+a/2],a/2,sz-a/2-i);
                memmove(&arr[i],t,(sz-i)*sizeof(int));
                free(t);
            }
        }
    }
    return 0;
}
//归并排序的迭代版本



int sort(int*arr,int sz)
{
	if(sz>1) {
		int a = sz/2;
		sort(arr,a);
        sort(&arr[a],sz-a);
		int* p = arrs_sort(arr,&arr[a],a,sz-a); 
		memmove(arr,p,sz*sizeof(int));
		free(p);
	}
	return 1;
}



int main()

{
	int arr[] = {1,5,8,3,2,4};
	merge_sort(arr,sizeof(arr)/sizeof(*arr));
	printf("%d",arr);
	return 0; 
}

